package com.wujunshen.algorithm.leetcode.divide.conquer;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @author frank woo(吴峻申) <br>
 *     email:<a href="mailto:frank_wjs@hotmail.com">frank_wjs@hotmail.com</a> <br>
 * @date 2022/7/25 21:31<br>
 */
public class 最接近原点的K个点 {
  public int[][] kClosest(int[][] points, int k) {
    if (k == points.length) {
      return points;
    }

    PriorityQueue<int[]> pq =
        new PriorityQueue<>(
            k,
            new Comparator<int[]>() {
              public int compare(int[] a, int[] b) {
                return (b[0] * b[0] + b[1] * b[1]) - (a[0] * a[0] + a[1] * a[1]);
              }
            });

    for (int[] point : points) {
      pq.add(point);
      if (pq.size() > k) pq.poll();
    }
    return pq.toArray(new int[0][0]);
  }
}
